/**
 * 给定一个头结点为 head 的非空单链表，返回链表的中间结点。
 * 如果有两个中间结点，则返回第二个中间结点。
 */

#include<vector>
using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};


// Solution 1:把链表转存入数组，这样就能获取下标 
class Solution_1 {
public:
    ListNode* middleNode(ListNode* head) {
        vector<ListNode*> L = {head};

        // back 得到数组的最后一个单元的引用
        while (L.back()->next != NULL)
        {
            L.push_back(L.back()->next);
        }

        // 中间节点的下标恰好为 长度/2
        return L[L.size()/2];
    }
};

// 单指针：一个指针，遍历两次，第一次统计节点个数，第二次遍历到中间 N/2 节点处
class Solution_2 {
public:
    ListNode* middleNode(ListNode* head) {
        // 统计长度
        int len = 0;
        ListNode * cur = head;
        while (cur != nullptr)
        {
            ++len;
            cur = cur->next;
        }
        
        cur = head;
        for(int i=0; i<len/2; i++){
            cur = cur->next;
        }
        return cur;
    }
};

// 快慢指针：慢指针slow一次走一步，快指针fast一次走两步
// 当fast到达链表末尾时，slow到达中间
class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        ListNode * fast = head;
        ListNode * slow = head;

        while (fast != NULL && fast->next != NULL)
        {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
        
    }
};